/* 
 * File:   main.cpp
 * Author: trunghpb
 *
 * Created on March 21, 2010, 10:30 PM
 ĐỀ SỐ 22

Cho đồ thị có hướng G =<V,E> gồm N đỉnh và M cạnh được biểu diễn dưới dạng danh sách kề trong file dske.in theo khuôn dạng sau:
•	Dòng đầu tiên ghi lại số tự nhiên N là số đỉnh của đồ thị;
•	N dòng kế tiếp mỗi dòng ghi lại danh sách kề của đỉnh tương ứng. Hai đỉnh trong cùng một danh sách kề được phân biệt với nhau bằng một hoặc vài kí tự trống, đỉnh không có cạnh nối với nó (đỉnh cô lập) được ghi giá trị 0.
 Hãy viết chương trình kiểm tra và đưa ra thông báo:
a)	“Đồ thị liên thông mạnh” nếu G liên thông mạnh;
b)	“Đồ thị liên thông yếu” nếu G không liên và G liên thông yếu;
c)	“Đồ thị không liên thông mạnh, không liên thông yếu” trong những trường hợp còn lại.

Ví dụ với đồ thị được biểu diễn dưới dạng danh sách kề dưới, kết quả thực hiện của chương trình là “ Đồ thị liên thông mạnh”.
dske.in
5
2
3	5
1	5
5
4

 */

#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

#define MAX 100
#define TRUE 1
#define FALSE 0

int a[MAX][MAX];
int N, sodinh;
int chuaxet[MAX];

void input(){

    for(int i=0; i<MAX; i++){
        for(int j=0; j<MAX; j++){
            a[i][j] = 0;
        }
    }

    FILE *fi;
    char line[MAX], so[10];
    int k;
    fi = fopen("dske.in", "r");
    fscanf(fi, "%d\n", &N);
    for(int i=0; i<N; i++){
        fgets(line, MAX, fi);
        k = 0;
        for(int t=0; t<strlen(line) + 1; t++){
            if (line[t]>= '0' && line[t] <= '9'){
                so[k++] = line[t];
            }else{
                if (k>0){
                    so[k] = 0;
                    int j = atoi(so);
                    a[i][j-1] = 1;
                }
                k = 0;
            }
        }
    }
    fclose(fi);
}
void init(){
    sodinh = 0;
    for(int i=0; i<N; i++){
        chuaxet[i] = TRUE;
    }
}
void bfs(int u){
    int queue[MAX];
    int dau = 0, cuoi = 0, t;
    queue[cuoi++] = u;chuaxet[u] = FALSE;sodinh++;

    do{
        t = queue[dau++];
        for(int v=0; v<N; v++){
            if (chuaxet[v] && a[t][v]){
                chuaxet[v] = FALSE;
                sodinh++;
                queue[cuoi++] = v;
            }
        }
    }while (dau<cuoi);
}

void vo_huong(){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if (a[i][j]){
                a[j][i] = 1;
            }
        }
    }
}

void kt_lienthong(){
    init();
    bfs(0);
    if (sodinh == N){
        printf("Do thi lien thong manh");
    }else{
        vo_huong();
        bfs(0);
        if (sodinh == N){
            printf("Do thi lien thong yeu");
        }else{
            printf("Do thi khong lien thong manh, khong lien thong yeu");
        }
    }
}

/*
 * 
 */
int main(int argc, char** argv) {
    input();
    kt_lienthong();
    return (EXIT_SUCCESS);
}

